package chapter03_binaryTree;

/**
 * 描述：
 *      给定一个数组，没有重复值，判断数组是否可能是二叉搜索树后序遍历的结果
 *      进阶：根据搜索二叉树后序遍历生成的数组，重构二叉树
 * @author hl
 * @date 2021/5/29 10:43
 */
public class IsPostArray {
    /**
     * 判断数组是否是搜索二叉树遍历的结果
     * 根据二叉树后序遍历的特点，
     *      最后一个元素就是当前二叉树的头结点，
     *      而当前结点左子树的值都分布在数组的左边，当前结点右子树的值都分布在数组的右边
     * 可以将数组分区后递归地进行判断
     * @param arr
     * @return
     */
    public boolean isPostArray(int[] arr){
        if (arr == null || arr.length == 0) {
            return false;
        }
        return isPost(arr, 0, arr.length - 1);
    }

    private boolean isPost(int[] arr, int start, int end) {
        if (start == end) {
            return true;
        }
        int less = -1;
        int more = end;
        for (int i = start; i < end; i++) {
            if (arr[end] > arr[i]) {
                less = i;
            }else{
                more = more == end ? i : more;
            }
        }
        if (less == -1 || more == end) {
            isPost(arr, 0, end - 1);
        }
        if (less != more - 1) {
            return false;
        }
        return isPost(arr, start, less) && isPost(arr, more, end - 1);
    }

    public Node posArrayToBST(int[] arr){
        if (arr == null || arr.length == 0) {
            return null;
        }
        return posToBST(arr, 0, arr.length - 1);
    }

    private Node posToBST(int[] arr, int start, int end) {
        if (start > end) {
            return null;
        }
        Node node = new Node(arr[end]);
        int less = -1;
        int more = end;
        for (int i = start; i < end; i++) {
            if (arr[end] > arr[i]) {
                less = i;
            }else{
                more = more == end ? i : more;
            }
        }
        node.left = posToBST(arr, start, less);
        node.right = posToBST(arr, more, end - 1);
        return node;
    }
}
